#include <NTL/ZZ.h>
#include <NTL/vec_ZZ.h>
#include <NTL/mat_ZZ.h>
#include <NTL/tools.h>
#include <NTL/RR.h>

#include <vector>

#include <stdlib.h>

//the number for the first column of our basis is 2^RANDOM_MAX
#define RANDOM_MAX 10 * dimension

NTL_CLIENT

struct vec {
  vec_ZZ v;
  ZZ mag_sq;
};


mat_ZZ randomBasis(int dimension);
vec randomVec(mat_ZZ &basis);

vec reduce(vec *v, vec *a);
ZZ mag_sq(vec_ZZ &v);

void setVec(vec*, vec_ZZ&);

//global variables for keeping time

unsigned long reduce_time;
unsigned long magnitude_time;
unsigned long randomVec_time;
unsigned long randomBasis_time;

/*
 * reduces v using a, that is, returning the smallest vector you can make 
 * subtracting or adding a to v
 */
vec reduce(vec *v, vec *a)
{
  clock_t begin = clock();
  ZZ c; //minimize v - c * a
  ZZ dot; //dot product of v and a
  vec ret;

  //find c such that v - c* a is minimized
  InnerProduct(dot, v->v, a->v); //dot = inner product
  //c = round((t * x)/(x * x) ) where * is dot product
  RoundToZZ(c, MakeRR(dot, 0)/MakeRR(a->mag_sq,0)); 

  ret.v = v->v - c * a->v;
  ret.mag_sq = v->mag_sq + c * c * a->mag_sq - 2 * c * dot;

  reduce_time += clock() - begin;

  return ret;
}

/*
 * Returns a random lattice vector using only 0, 1 given lattice L
 */
vec randomVec(mat_ZZ &basis)
{
  clock_t begin = clock();
  vector<long> v;//0 1 vector
  vec ret;
  ZZ zero;
  zero = 0;

  //set v to all 0 or 1s randomly
  for(int i = 0; i < basis.NumCols(); i++)
  {
    int i = rand()%2;
    v.push_back(i);
  }
  //initialize ret to all 0s
  for(int i = 0; i < basis.NumCols(); i++)
    append(ret.v, zero);
  for(int i = 0; i < ret.v.length(); i++)
  {
    if(v.at(i)) //if it's 1 we have to add it to ret
      ret.v = ret.v + basis[i];
  }
  ret.mag_sq = mag_sq(ret.v);
  if(ret.mag_sq == 0) 
    return randomVec(basis);

  randomVec_time += (clock() - begin);
  return ret;
}

ZZ mag_sq(vec_ZZ &a)
{
  clock_t begin = clock();
  ZZ sumsquares;
  for(int i = 0; i < a.length(); i++)
  {
    sumsquares+= sqr(a[i]);
  }

  magnitude_time += clock() - begin;
  return sumsquares;
}

/*
 * Returns a random basis, uses RANDOM_MAX to set the value at [0,0], and 
 * is a subset sum matrix
 */
mat_ZZ randomBasis(int dimension)
{
  clock_t begin = clock();
  mat_ZZ ret;
  vec_ZZ temp;

  ZZ m = power_ZZ(2, RANDOM_MAX);
  ZZ z;
  z = 0;

  //set them both to be right dimension
  for(int i = 0; i < dimension; i++)
    append(temp, z);
  ret.SetDims(dimension, dimension);
  //initialize all to 0
  for(int i = 0; i < dimension; i++)
  {
    for(int i = 0; i < dimension; i++)
    {
      ret[i][i] = 0;
    }
  }
  ZZ s;
  s = time(0);
  SetSeed(s);
  ret[0][0] = m;
  for(int i = 1; i < dimension; i++)
  {
    ret[i][0] = RandomBnd(m);
  }
  for(int i = 1; i < dimension; i++)
  {
    ret[i][i] = 1;
  }

  randomBasis_time += (clock() - begin);
  return ret;
}


void setVec(vec *a, vec_ZZ &b)
{
  a->v = b;
  a->mag_sq = mag_sq(b);
}
